// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

// Package gcprog为压缩GC指针位图实现一个编码器，
// 被称为GC程序。
// None
// 程序格式
// None
// GC程序对表示对象中标量或指针字的0位和1位序列进行编码。
// 编码是一个简单的Lempel-Ziv程序，使用代码来发出文字位并重复
// 最后n位c次。
// None
// 可能的代码是：
// None
// 00000000：停止
// 0nnnnn:从下一个（n+7）/8字节（最低有效位在前）复制n位
// 10000000 n c：重复之前的n位c次；n、 c是各种各样的
// 1nnn c：重复前面的n位c次；c是一个变种
// None
// 当数字n和c跟在代码后面时，它们被编码为变量
// 使用与encoding/binary的Uvarint相同的编码。
// None
package gcprog

import (
	"fmt"
	"io"
)

const progMaxLiteral = 127 // 文字n位代码的最大n

// 编写器是GC程序的编码器。
// None
// Writer的典型用法是调用Init，或者调用Debug，
// 进行一系列Ptr、Advance、Repeat和Append调用
// 描述数据类型，然后最后调用End。
type Writer struct {
	writeByte func(byte)
	index     int64
	b         [progMaxLiteral]byte
	nb        int
	debug     io.Writer
	debugBuf  []byte
}

// Init初始化w以编写新的GC程序
// 通过为程序中的每个字节调用writeByte。
func (w *Writer) Init(writeByte func(byte)) {
	w.writeByte = writeByte
}

// 调试使编写器将调试跟踪打印出来
// 在以后调用Ptr、Advance和End等方法时。
// 它还支持在编码过程中进行调试检查。
func (w *Writer) Debug(out io.Writer) {
	w.debug = out
}

// BitIndex返回到目前为止写入位流的位数。
func (w *Writer) BitIndex() int64 {
	return w.index
}

// 字节将字节x写入输出。
func (w *Writer) byte(x byte) {
	if w.debug != nil {
		w.debugBuf = append(w.debugBuf, x)
	}
	w.writeByte(x)
}

// 结束标记程序的结束，写入任何剩余字节。
func (w *Writer) End() {
	w.flushlit()
	w.byte(0)
	if w.debug != nil {
		index := progbits(w.debugBuf)
		if index != w.index {
			println("gcprog: End wrote program for", index, "bits, but current index is", w.index)
			panic("gcprog: out of sync")
		}
	}
}

// Ptr在给定的位索引处向位流发射1。
// 也就是说，它记录了对象内存中索引的第四个字是指针。
// 当前索引和新索引之间的任何位
// 设置为零，表示对应的单词是标量。
func (w *Writer) Ptr(index int64) {
	if index < w.index {
		println("gcprog: Ptr at index", index, "but current index is", w.index)
		panic("gcprog: invalid Ptr index")
	}
	w.ZeroUntil(index)
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: ptr at %d\n", index)
	}
	w.lit(1)
}

// 是否应该重复报告是否值得
// 使用一个重复来描述每个n位的c元素，
// 与仅发送n位描述的c拷贝相比。
func (w *Writer) ShouldRepeat(n, c int64) bool {
	// 我们是否应该直接而不是直接地布置这些部分
	// 将它们编码为重复？当然，如果count==1，
	// 既然没有什么可重复的，而且如果总
	// 类型的普通指针位的大小将适合
	// 4或更少字节，因为使用重复将需要
	// 刷新当前位加上至少一个字节
	// 重复大小和一个用于重复计数。
	return c > 1 && c*n > 4*8
}

// Repeat发出重复描述的指令
// 最后n个单词中的c次（包括初始描述，共c+1次）。
func (w *Writer) Repeat(n, c int64) {
	if n == 0 || c == 0 {
		return
	}
	w.flushlit()
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: repeat %d × %d\n", n, c)
	}
	if n < 128 {
		w.byte(0x80 | byte(n))
	} else {
		w.byte(0x80)
		w.varint(n)
	}
	w.varint(c)
	w.index += n * c
}

// ZeroTill将零添加到位流，直到达到给定索引；
// 也就是说，它记录从最近的指针到
// 索引的第四个单词是标量。
// ZeroTill通常是在准备重复、追加或结束调用时调用的。
func (w *Writer) ZeroUntil(index int64) {
	if index < w.index {
		println("gcprog: Advance", index, "but index is", w.index)
		panic("gcprog: invalid Advance index")
	}
	skip := (index - w.index)
	if skip == 0 {
		return
	}
	if skip < 4*8 {
		if w.debug != nil {
			fmt.Fprintf(w.debug, "gcprog: advance to %d by literals\n", index)
		}
		for i := int64(0); i < skip; i++ {
			w.lit(0)
		}
		return
	}

	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: advance to %d by repeat\n", index)
	}
	w.lit(0)
	w.flushlit()
	w.Repeat(1, skip-1)
}

// Append将给定的GC程序发送到当前输出中。
// 调用者断言程序发出n位（描述n个字），
// 如果这不是真的，就追加恐慌。
func (w *Writer) Append(prog []byte, n int64) {
	w.flushlit()
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: append prog for %d ptrs\n", n)
		fmt.Fprintf(w.debug, "\t")
	}
	n1 := progbits(prog)
	if n1 != n {
		panic("gcprog: wrong bit count in append")
	}
	// prog的最后一个字节终止程序。
	// 不要发射，否则我们自己的程序就会结束。
	for i, x := range prog[:len(prog)-1] {
		if w.debug != nil {
			if i > 0 {
				fmt.Fprintf(w.debug, " ")
			}
			fmt.Fprintf(w.debug, "%02x", x)
		}
		w.byte(x)
	}
	if w.debug != nil {
		fmt.Fprintf(w.debug, "\n")
	}
	w.index += n
}

// progbits返回由程序p编码的位流的长度。
func progbits(p []byte) int64 {
	var n int64
	for len(p) > 0 {
		x := p[0]
		p = p[1:]
		if x == 0 {
			break
		}
		if x&0x80 == 0 {
			count := x &^ 0x80
			n += int64(count)
			p = p[(count+7)/8:]
			continue
		}
		nbit := int64(x &^ 0x80)
		if nbit == 0 {
			nbit, p = readvarint(p)
		}
		var count int64
		count, p = readvarint(p)
		n += nbit * count
	}
	if len(p) > 0 {
		println("gcprog: found end instruction after", n, "ptrs, with", len(p), "bytes remaining")
		panic("gcprog: extra data at end of program")
	}
	return n
}

// readvarint从p读取变量，返回值和p的剩余部分。
func readvarint(p []byte) (int64, []byte) {
	var v int64
	var nb uint
	for {
		c := p[0]
		p = p[1:]
		v |= int64(c&^0x80) << nb
		nb += 7
		if c&0x80 == 0 {
			break
		}
	}
	return v, p
}

// lit将单个文字位添加到w。
func (w *Writer) lit(x byte) {
	if w.nb == progMaxLiteral {
		w.flushlit()
	}
	w.b[w.nb] = x
	w.nb++
	w.index++
}

// varint发出x的varint编码。
func (w *Writer) varint(x int64) {
	if x < 0 {
		panic("gcprog: negative varint")
	}
	for x >= 0x80 {
		w.byte(byte(0x80 | x))
		x >>= 7
	}
	w.byte(byte(x))
}

// flushlit刷新所有挂起的文本位。
func (w *Writer) flushlit() {
	if w.nb == 0 {
		return
	}
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: flush %d literals\n", w.nb)
		fmt.Fprintf(w.debug, "\t%v\n", w.b[:w.nb])
		fmt.Fprintf(w.debug, "\t%02x", byte(w.nb))
	}
	w.byte(byte(w.nb))
	var bits uint8
	for i := 0; i < w.nb; i++ {
		bits |= w.b[i] << uint(i%8)
		if (i+1)%8 == 0 {
			if w.debug != nil {
				fmt.Fprintf(w.debug, " %02x", bits)
			}
			w.byte(bits)
			bits = 0
		}
	}
	if w.nb%8 != 0 {
		if w.debug != nil {
			fmt.Fprintf(w.debug, " %02x", bits)
		}
		w.byte(bits)
	}
	if w.debug != nil {
		fmt.Fprintf(w.debug, "\n")
	}
	w.nb = 0
}
